package leetcode.greed;

import java.util.Arrays;

import static jdk.nashorn.internal.runtime.regexp.joni.encoding.CharacterType.D;

/**
 * Created by zxc on 2018/10/4.
 * 两个相邻元素的差恰好正负（负正）出现，求一随机序列的最长子序列满足摇摆序列的特点  利用状态机的思想去做题
 */
public class WiggleSubsequence {
    static final int BEGIN =0;
    static final int UP =1;
    static final int DOWN =2;
    /**/
    private static int wiggleMaxLength(int[] arr) {
        if (arr.length < 2) {
            return arr.length;
        }
        int STATE = BEGIN;
        int maxLength = 1;
        for(int i = 1;i < arr.length; i++) {
            switch (STATE) {
                case BEGIN:
                    if (arr[i - 1] < arr[i]) {
                        STATE = UP;
                        maxLength ++;
                    } else if (arr[i - 1] > arr[i]) {
                        STATE = DOWN;
                        maxLength ++;
                    }
                    break;
                case UP:
                    if (arr[i - 1] > arr[i]) {
                        STATE = DOWN;
                        maxLength++;
                    }
                    break;
                case DOWN:
                    if (arr[i - 1] < arr[i]) {
                        STATE = UP;
                        maxLength++;
                    }
                    break;
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {1,17,5,10,13,15,10,5,16,8};

        int number = wiggleMaxLength(arr);

        System.out.println("摇摆序列长度：" + number);
    }
}
